package leetcode.editor.cn;

//给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 
//
// 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "1 + 1"
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：s = " 2-1 + 2 "
//输出：3
// 
//
// 示例 3： 
//
// 
//输入：s = "(1+(4+5+2)-3)+(6+8)"
//输出：23
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 3 * 10⁵ 
// s 由数字、'+'、'-'、'('、')'、和 ' ' 组成 
// s 表示一个有效的表达式 
// '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效) 
// '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的) 
// 输入中不存在两个连续的操作符 
// 每个数字和运行的计算将适合于一个有符号的 32位 整数 
// 
// Related Topics 栈 递归 数学 字符串 👍 739 👎 0

import java.util.Stack;

//Java：【224】 - 基本计算器
public class BasicCalculator_224{
    public static void main(String[] args) {
        Solution solution = new BasicCalculator_224().new Solution();
                // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int calculate(String s) {
        char[] chars = s.toCharArray();
        int res=0;
        Stack<Integer> sign = new Stack<>();
        int num =0;
        char preOperation ='+'; // 前一个+/-
        sign.push(1);
        for (int i = 0; i < chars.length; i++) {
            if(Character.isDigit(chars[i])){
                num = num*10+chars[i]-'0';
            }
            if(!Character.isDigit(chars[i]) && chars[i]!=' ' || i==chars.length-1){
                char ch = chars[i];
                if (ch == '(') {
                    sign.push(sign.peek() * (preOperation == '-' ? -1 : 1));
                    preOperation = '+';
                } else { // 遇到')' 或 '+' 或 '-' 或 最后，均为添加数字
                    res=res + num * sign.peek() * (preOperation == '-' ? -1 : 1);
                    if (ch == ')') sign.pop(); // 标识符回退
                    num = 0;
                    preOperation = ch; // 若当前为')',由于num=0，无论后面是什么符号，入栈的都只会是0
                }
            }
//            System.out.println(nums);
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
